package org.lql.algo.codecrush.week004;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * @author: liangqinglong
 * @date: 2025-08-01 17:50
 * @description: 42. 接雨水 <a href="https://leetcode.cn/problems/trapping-rain-water/description/">...</a>
 **/
public class Trap {

	/**
	 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
	 */
	public int trap(int[] height) {
		// 单调栈，存放柱子的块（包含高度和宽度）
		Stack<Rect> stack = new Stack<>();
		int ans = 0;
		for (int h : height) {
			// 累加被弹出的柱子的总宽度，用于计算当前凹槽的宽度
			int accumulatedWidth = 0;
			// 当前柱子高度大于栈顶，说明右边界出现，可能形成积水
			while (!stack.isEmpty() && stack.peek().height <= h) {
				// 凹槽的底部柱子
				Rect rect = stack.pop();
				// 记录底部高度
				int bottom = rect.height;
				// 累加底部的宽度
				accumulatedWidth += rect.width;
				// 如果左边已经没有柱子了，无法形成凹槽，跳过
				if (stack.isEmpty()) {
					continue;
				}
				// 以bottom为底的水最高可到up（左右两侧高度的min）// 左右两边高度较小者作为水的上边界（挡水板）
				int up = Math.min(h, stack.peek().height);
				// 高度差就是积水深度，乘以宽度就是体积
				ans += accumulatedWidth * (up - bottom);
			}
			// 当前柱子与之前低矮柱子合并，形成新的区块压入栈
			stack.push(new Rect(accumulatedWidth + 1, h));
		}
		return ans;
	}

	static class Rect {
		int width;
		int height;

		public Rect(int width, int height) {
			this.width = width;
			this.height = height;
		}
	}

	public int trapGpt(int[] height) {
		int water = 0;
		Deque<Integer> stack = new ArrayDeque<>();

		for (int i = 0; i < height.length; i++) {
			// 当前高度大于栈顶，说明可以接水了
			while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
				int bottom = stack.pop(); // 取出低洼处
				if (stack.isEmpty()) {
					break; // 左边没有更高的柱子，无法接水
				}

				int left = stack.peek(); // 左边界
				int width = i - left - 1; // 宽度
				int boundedHeight = Math.min(height[i], height[left]) - height[bottom]; // 高度

				water += width * boundedHeight;
			}

			stack.push(i); // 把当前索引加入栈中
		}

		return water;
	}

	public static void main(String[] args) {
		int[] height = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
		Trap trap = new Trap();
		System.out.println(trap.trap(height));
		System.out.println(trap.trapGpt(height));
	}
}
